package leetcode.median;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * ClassName: $524_FindLongestWord
 * Description:
 * date: 2021-10-23 23:26
 *
 * @author liyifan
 */
public class $524_FindLongestWord {
    public String findLongestWord(String s, List<String> dictionary) {
        ArrayList<String> res = new ArrayList<>();
        for (String tmp:dictionary) {
            for (int i = 0, j = 0;i < s.length() && j < tmp.length();) {
                if (s.charAt(i) == tmp.charAt(j)) {
                    i++;
                    j++;
                    if (j == tmp.length()) {
                        res.add(tmp);
                        break;
                    }
                } else {
                    i++;
                }
            }
        }
        res.sort((s1, s2) -> {
            if (s1.length() != s2.length())
                return s2.length() - s1.length();
            else
                return s1.compareTo(s2);
        });
        System.out.println(res.toString());
        return res.size() == 0 ? "" : res.get(0);
    }

    public String findLongestWord2(String s, List<String> dictionary) {
        dictionary.sort((s1, s2) -> {
            if (s1.length() != s2.length())
                return s2.length() - s1.length();
            else
                return s1.compareTo(s2);
        });
        int n = s.length();
        for (String tmp:dictionary) {
            int m = tmp.length();
            for (int i = 0,j = 0; i < n && j < m; ) {
                if (s.charAt(i) == tmp.charAt(j)){
                    i++;
                    j++;
                    if (j == m)
                        return tmp;

                } else {
                    i++;
                }
            }
        }

        return "";
    }
}
